package LeetCode热题HOT100;

public class p64最小路径和 {

    public int minPathSum(int[][] grid) {
        //动态规划之优化空间复杂度
        //不建立 dp矩阵浪费额外空间，直接遍历 grid[i][j]修改即可
        //因为grid矩阵元素中被覆盖为 dp元素后（都处于当前遍历点的左上方），不会再被使用到
        for (int i = 0; i <grid.length ; i++) {
            for (int j = 0; j <grid[0].length; j++) {
                if (i==0 && j==0) continue;
                else if (i==0) {
                    grid[i][j]=grid[i][j]+grid[i][j-1];
                }else if (j==0) {
                    grid[i][j]=grid[i][j]+grid[i-1][j];
                }else {
                    grid[i][j]=grid[i][j]+Math.min(grid[i-1][j],grid[i][j-1]);
                }
            }
        }
        return grid[grid.length-1][grid[0].length-1];
    }

    public int minPathSum1(int[][] grid) {
        //动态规划
        int row=grid.length;
        int column=grid[0].length;
        int[][] dp=new int[row][column];

        for (int i = 0; i <row ; i++) {
            for (int j = 0; j <column ; j++) {
                if (i==0 && j==0) {
                    dp[i][j]=grid[i][j];
                }else if (i==0) {
                    //上边界的元素，都只能从左边到达
                    dp[i][j]=grid[i][j]+dp[i][j-1];
                }else if (j==0) {
                    //左边界的元素，都只能从上边到达
                    dp[i][j]=grid[i][j]+dp[i-1][j];
                }else {
                    //可能从左边到达，可能从上边到达
                    dp[i][j]=grid[i][j]+Math.min(dp[i-1][j],dp[i][j-1]);
                }
            }
        }

        return dp[row-1][column-1];
    }
}
